package com.jxm.graph;

import com.jxm.linear.Queue;

/**
 * @Author: jxm
 * @Description: 加权无向图的实现
 * @Date: 2022/8/8 22:00
 * @Version: 1.0
 */
public class EdgeWeightedGraph {

    //记录顶点数量
    private final int V;
    //记录边数量
    private int E;
    //邻接表
    private Queue<Edge>[] adj;

    /**
     * 创建一个含有V个顶点的空加权无向图
     * @param V
     */
    public EdgeWeightedGraph(int V){
        //初始化顶点数量
        this.V = V;
        // 初始化边的数量
        this.E = 0;
        // 初始化邻接表
        this.adj = new Queue[V];
        // 初始化邻接表中的空队列
        for (int i = 0; i < adj.length; i++) {
            adj[i] = new Queue<Edge>();
        }
    }

    /**
     * 获取图中顶点的数量
     * @return
     */
    public int V() { return V; }

    /**
     * 获取图中边的数量
     * @return
     */
    public int E() { return E; }

    /**
     * 向加权无向图中添加一条边e
     * @param e
     */
    public void addEdge(Edge e){
        //需要让边e同时出现在e这个边的两个顶点的邻接表中
        int v = e.either();
        int w = e.other(v);

        adj[v].enqueue(e);
        adj[w].enqueue(e);

        //边+1
        E++;
    }


    /**
     * 获取和顶点v关联的所有边
     * @param v
     * @return
     */
    public Queue<Edge> adj(int v){
        return adj[v];
    }


    /**
     * 获取加权无向图的所有边
     * @return
     */
    public Queue edges(){
        //创建一个队列存储所有的边
        Queue<Edge> edges = new Queue<>();
        //通丙图中的每一个顶点，找到该顶点的邻接表，邻接表中存储了该顶点矣联的每一条边
        //因为这是无向图，所以同一条边同时出现在了它关联的两个顶点的邻接表中，需要让一条边只保存一次
        for (int v = 0; v < V; v++) {
            //遍历v顶点的邻接表，找到每一条和v矣联的边
            for (Edge e : this.adj(v)) {
                if(e.other(v) < v){
                    edges.enqueue(e);
                }
            }
        }

        return edges;
    }
}
